/**
 * 给定二维01数组，问用三个不相交的横平竖直的矩形将所有1包含的最小面积
 * 注意到N和M只有30。
 * 因为矩形是横平竖直的，矩形各自所在区域的分布只有6种情况。
 * 第一种，   第二种,   第三种
 * AAAA      AAAA     BBBCCC
 * BBBB      BBCC     AAAAAA
 * CCCC
 * 还有三种是将上述三种情况做一个转置。
 * 因此可以枚举两条分界线，然后暴力枚举每一个区域
 * O((NM)^2)
 * 可以用前缀和降一个数量级变为O(NM)
 */
class Solution {

int N, M;
vector<vector<int>> Board;

public:
    int minimumSum(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();
        Board.assign(grid.begin(), grid.end());
        
        int ans = procHH();
        ans = min(ans, procHS());
        ans = min(ans, procSH());

        Board.assign(M, vector<int>(N, 0));
        for(int i=0;i<N;++i)for(int j=0;j<M;++j)Board[j][i] = grid[i][j];
        swap(N, M);

        ans = min(ans, procHH());
        ans = min(ans, procHS());
        ans = min(ans, procSH());

        return ans;
    }

    int procHH(){
        int ans = N * M;
        for(int i=0;i<N;++i)for(int j=i+1;j+1<N;++j){
            auto tmp = calc(0, 0, i, M - 1);
            tmp += calc(i + 1, 0, j, M - 1);
            tmp += calc(j + 1, 0, N - 1, M - 1);
            ans = min(ans, tmp);
        }
        return ans;
    }

    int procHS(){
        int ans = N * M;
        for(int i=0;i+1<N;++i){
            auto tmp = calc(0, 0, i, M - 1);
            for(int j=0;j+1<M;++j){
                auto tt = tmp +  calc(i + 1, 0, N - 1, j);
                tt += calc(i + 1, j + 1, N - 1, M - 1);
                ans = min(ans, tt);
            }
        }
        return ans;
    }

    int procSH(){
        int ans = N * M;
        for(int i=0;i+1<N;++i){
            auto tmp = calc(i + 1, 0, N - 1, M - 1);
            for(int j=0;j+1<M;++j){
                auto tt = tmp +  calc(0, 0, i, j);
                tt += calc(0, j + 1, i, M - 1);
                ans = min(ans, tt);
            }
        }
        return ans;
    }

    int calc(int top, int left, int bottom, int right){
        int lmost = 10000, tmost = 10000, rmost = -1, bmost = -1;
        for(int i=top;i<=bottom;++i)for(int j=left;j<=right;++j){
            if(1 == Board[i][j]){
                lmost = min(lmost, j);
                rmost = max(rmost, j);
                tmost = min(tmost, i);
                bmost = max(bmost, i);
            }
        }
        if(-1 == rmost) return 0;
        return (rmost - lmost + 1) * (bmost - tmost + 1);
    }
};